package Week.LC;

import common.ListNode;
import org.junit.Test;

import java.util.*;

public class Solution01 {

    public int game(int[] guess, int[] answer) {
        int result = 0;
        for (int i = 0; i < guess.length; i++) {
            if (guess[i] == answer[i]) {
                result++;
            }
        }
        return result;
    }

    public int[] fraction(int[] cont) {
        int[] result = new int[2];
        result[0] = cont[cont.length - 1];
        result[1] = 1;
        for (int i = cont.length - 2; i >= 0; i--) {
            int temp = result[0];
            result[0] = result[1];
            result[1] = temp;
            result[0] = result[0] + cont[i] * result[1];
        }
        int x = gcd(result[0], result[1]);
        if (x != 0) {
            result[0] = result[0] / x;
            result[1] = result[1] / x;
        }
        return result;

    }

    private static int gcd(int x, int y) {
        if (y == 0)
            return x;
        else
            return gcd(y, x % y);
    }


    public boolean robot(String command, int[][] obstacles, int x, int y) {
        int curX = 0;
        int curY = 0;
        char[] chars = command.toCharArray();
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] obstacle : obstacles) {
            if (map.containsKey(obstacle[0])) {
                map.get(obstacle[0]).add(obstacle[1]);
            } else {
                Set<Integer> tempSet = new HashSet<>();
                tempSet.add(obstacle[1]);
                map.put(obstacle[0], tempSet);
            }
        }
        while (true) {
            for (char aChar : chars) {
                if (aChar == 'U') {
                    curY++;
                } else {
                    curX++;
                }

                if (curX > x || curY > y) {
                    return false;
                }
                if (curX == x && curY == y) {
                    return true;
                }
                if (map.containsKey(curX)) {
                    Set<Integer> tempMap = map.get(curX);
                    if (tempMap != null && tempMap.contains(curY)) {
                        return false;
                    }
                }
            }
        }
    }


    public int[] bonus(int n, int[][] leadership, int[][] operations) {
        Map<Integer, Map<Integer, CoinNode>> map = new HashMap<>();
        Map<Integer, Integer> leaderMap = new HashMap<>();
        Map<Integer, CoinNode> tempMap1 = new HashMap<>();
        tempMap1.put(1, new CoinNode());
        map.put(0, tempMap1);
        leaderMap.put(1, 0);
        for (int[] ship : leadership) {
            leaderMap.put(ship[1], ship[0]);
            if (map.containsKey(ship[0])) {
                map.get(ship[0]).put(ship[1], new CoinNode());
            } else {
                Map<Integer, CoinNode> tempMap = new HashMap<>();
                tempMap.put(ship[1], new CoinNode());
                map.put(ship[0], tempMap);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int[] operation : operations) {
            switch (operation[0]) {
                case 1:
                    action1(map, leaderMap, operation[1], operation[2]);
                    break;
                case 2:
                    action2(map, leaderMap, operation[1], operation[2]);
                    break;
                case 3:
                    result.add(action3(map, leaderMap, operation[1]));
                    break;
            }
        }
        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        return resultArray;

    }

    private void action1(Map<Integer, Map<Integer, CoinNode>> map, Map<Integer, Integer> leaderMap, Integer userId, Integer coinNum) {
        Integer leader = leaderMap.get(userId);
        CoinNode coinNode=map.get(leader).get(userId);
        coinNode.coin= (coinNode.coin+coinNum) % 1000000007;
        coinNode.childSum=(coinNode.childSum+coinNum) % 1000000007;

        while (leaderMap.containsKey(userId)){
            Integer tempLeader = leaderMap.get(userId);
            CoinNode tempCoinNode=map.get(tempLeader).get(userId);
            tempCoinNode.coin= (tempCoinNode.coin+coinNum) % 1000000007;
            tempCoinNode.childSum=(tempCoinNode.childSum+coinNum) % 1000000007;
            userId=tempLeader;
        }
    }

    private void action2(Map<Integer, Map<Integer, CoinNode>> map, Map<Integer, Integer> leaderMap, Integer userId, Integer coinNum) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(userId);
        Integer leader = leaderMap.get(userId);
        map.get(leader).get(userId).coin = (map.get(leader).get(userId).coin + coinNum) % 1000000007;
        while (queue.size() != 0) {
            int curUserId = queue.poll();
            Map<Integer, CoinNode> tempMap = map.get(curUserId);
            if(tempMap==null){
                continue;
            }
            for (Map.Entry<Integer, CoinNode> entry : tempMap.entrySet()) {
                queue.add(entry.getKey());
                entry.getValue().coin = (entry.getValue().coin + coinNum) % 1000000007;
            }
        }
    }

    private Integer action3(Map<Integer, Map<Integer, CoinNode>> map, Map<Integer, Integer> leaderMap, Integer userId) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(userId);
        Integer leader = leaderMap.get(userId);
        Long result = map.get(leader).get(userId).coin;

        while (queue.size() != 0) {
            int curUserId = queue.poll();
            Map<Integer, CoinNode> tempMap = map.get(curUserId);
            if(tempMap==null){
                continue;
            }
            for (Map.Entry<Integer, CoinNode> entry : tempMap.entrySet()) {
                queue.add(entry.getKey());
                result = (result + entry.getValue().coin) % 1000000007;
            }
        }
        return Integer.parseInt(result + "");
    }

    public class CoinNode {
        public long coin;

        public long childSum;

        public CoinNode() {
            coin = 0;
            childSum=0;
        }

    }

    @Test
    public void test() {
        int n = 6;
        int[][] leadership = new int[][]{{1, 2}, {1, 6}, {2, 3}, {2, 5}, {1, 4}};
        int[][] operations = new int[][]{{1, 1, 500}, {2, 2, 50}, {3, 1}, {2, 6, 15}, {3, 1}};
        System.out.println(Arrays.toString(bonus(n, leadership, operations)));
      /* int[] t=new int[]{4,2,1,3};
       minimumAbsDifference(t);*/
        //    System.out.println(nthUglyNumber(3, 2, 3, 5));
        //    System.out.println(nthUglyNumber(4, 2, 3, 4));
        //      System.out.println(nthUglyNumber(5, 2, 11, 13));
        // System.out.println(nthUglyNumber(1000000000, 2, 217983653, 336916467));
        // System.out.println(reverseParentheses(test1));
        // System.out.println(reverseParentheses(test1));
        //  System.out.println(reverseParentheses(test3));

    }
}
